#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    vector<vector<string>> ret;
    vector<string> path;
    vector<bool> col;
    vector<bool> dig1;
    vector<bool> dig2;
    int n;

    vector<vector<string>> solveNQueens(int _n)
    {
        n = _n;
        col.resize(_n);
        dig1.resize(2*_n);
        dig2.resize(2 * _n);
        string str;
        while (_n--)
            str += '.';

        for (int i = 0; i < n; i++)
            path.push_back(str.c_str());
        dfs(0);
        return ret;
    }

    void dfs(int pos)
    {
        if (pos == n)
        {
            ret.push_back(path);
            return;
        }

        for (int i = 0; i < n; i++)
        {
            if (!col[i] && !dig1[pos - i + n] && !dig2[pos + i])
            {
                path[pos][i] = 'Q';
                col[i] = true;
                dig1[pos - i + n] = true;
                dig2[pos + i] = true;
                dfs(pos + 1);
                path[pos][i] = '.';
                col[i] = false;
                dig1[pos - i + n] = false;
                dig2[pos + i] = false;
            }

        }
    }
};

int main()
{
    Solution s;
    s.solveNQueens(4);
    return 0;
}